package club.xiaojiawei.binarytree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/10/22 8:13 PM
 * @question 429. N 叉树的层序遍历
 * @description 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 */
public class LevelOrder429 {

    public static void main(String[] args) {
        Node left = new Node(3, List.of(new Node(5), new Node(6)));
        Node middle = new Node(2, List.of(new Node(7), new Node(8)));
        Node root = new Node(1, List.of(left, middle, new Node(4)));
        List<List<Integer>> result = levelOrder(root);
        System.out.println(result);
    }

    /**
     * BFS+队列
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(Node root) {
        ArrayList<List<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        LinkedList<List<Node>> queue = new LinkedList<>();
        result.add(List.of(root.val));
        if (root.children == null){
            return result;
        }
        queue.add(root.children);
        int size;
        while ((size = queue.size()) > 0){
            ArrayList<Integer> son = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                List<Node> current = queue.pop();
                for (Node node : current) {
                    son.add(node.val);
                    if (node.children != null){
                        queue.add(node.children);
                    }
                }
            }
            if (son.size() > 0){
                result.add(son);
            }
        }
        return result;
    }

    static List<List<Integer>> result = new ArrayList<>();

    /**
     * 民间-递归+DFS
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder2(Node root) {
        dfs(root,0);
        return result;
    }

    public static void dfs(Node root,int depth){
        if(root == null){
            return;
        }
        depth++;
        if(result.size() < depth){
            List<Integer> list = new ArrayList();
            result.add(list);
        }
        result.get(depth - 1).add(root.val);
        for(int i = 0;i < root.children.size();i++){
            dfs(root.children.get(i),depth);
        }
    }

    static class Node {
        public int val;
        public List<Node> children;
        public Node() {}
        public Node(int _val) {
            val = _val;
        }
        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}
